/**
 * 
 */
package com.gwcloud.leetcode.hot100;

/**
 * @ClassName   : Leetcode0096 
 * @author      : ganwei 
 * @date        : 2020年5月20日
 * @Description : Leetcode0096 不同的二叉搜索树
 */
public class Leetcode0096 {
	/**
	 * -解题思路，动态规划,该动态规划有点不会
	 */
    public int numTrees(int n) {
    	int[] g = new int[n+1];
    	g[0] = 1;
    	g[1] = 1;
    	for(int i = 2; i <= n; i++){
    		for(int j = 0; j < i; j++){
    			g[i] += g[j]*g[i-j-1];
    		}
    	}
    	
    	return g[n];
    }
}
